package algorithm.dynamic;

import java.util.ArrayList;
import java.util.List;

/**
 * @author bingo
 * @Description
 * @Date 2018/6/18
 */
public class Fibonacci {

    private static List<Integer>  numberList = new ArrayList<>();

    public  static  int  calculate(int n){
        if(n==1){
            return 1;
        }
        if(n==2){
            return 1;
        }

        if(numberList.get(n)==-1){
            numberList.set(n,calculate(n-1)+calculate(n-2));
        }
        return  numberList.get(n);

    }
    public static  int calculate2(int n){
        Integer[] a = new Integer[n+1];
        a[1] = 1;
        a[2] = 1;
        for(int i=3;i<=n;i++){
            a[i] = a[i-1]+a[i-2];
        }

        return  a[n];

    }

    public static void main(String[] args) {

        int n = 60;

        for(int i=0;i<n+1;i++){
            numberList.add(i,-1);
        }

        long startTime = System.currentTimeMillis();

        System.out.println(Fibonacci.calculate2(n));

        long endTime = System.currentTimeMillis();

        System.out.println("耗时:"+(endTime-startTime)/1000.0);

        long startTime2 = System.currentTimeMillis();
        System.out.println(Fibonacci.calculate(n));
        long endTime2 = System.currentTimeMillis();

        System.out.println("耗时:"+(endTime2-startTime2)/1000.0);
        System.out.println();
    }
}
